#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickselect(nums, 0, nums.size() - 1, nums.size() - k);
    }
private:
    int quickselect(vector<int>& nums, int left, int right, int k) {
        if (left == right)return nums[left];
        int randomIndex = left + rand() % (right - left + 1);
        swap(nums[randomIndex], nums[right]);
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[right]);
        if (k == i) { return nums[i]; }
        else if (k < i) { return quickselect(nums, left, i - 1, k); }
        else { return quickselect(nums, i + 1, right, k); }
    }
};
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;

        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        return minHeap.top();
    }
};
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        return quickselect(nums, 0, nums.size() - 1, nums.size() - k);
    }
private:
    int quickselect(vector<int>& nums, int left, int right, int k) {
        if (left == right)return nums[left];
        int randomIndex = left + rand() % (right - left + 1);
        int pivot = nums[right];
        int i = left;
        int j = left;
        int m = right;
        while (j <= m) {
            if (nums[j] < pivot) {
                swap(nums[i], nums[j]);
                i++;
                j++;
            }
            else if (nums[j] > pivot) {
                swap(nums[j], nums[m]);
                m--;
            }
            else {
                j++;
            }
        }
        if (k == i) { return nums[i]; }
        else if (k < i) { return quickselect(nums, left, i - 1, k); }
        else { return quickselect(nums, i + 1, right, k); }
    }
};